#include <bits/stdc++.h>

using namespace std;

// 基数排序
// 测试链接 : https://leetcode.cn/problems/sort-an-array/

class Solution 
{
private:
    // 可以设置进制，不一定10进制，随你设置
    static const int BASE = 10000;
    static const int MAXN = 50001;
    int help[MAXN];
    int cnts[BASE];

    // 返回number在BASE进制下有几位
    int bits(int number)
    {
        int ans = 0;
        while(number > 0)
        {
            ++ans;
            number /= BASE;
        }
        return ans;
    }

	// 基数排序核心代码
	// arr内要保证没有负数
	// n是arr的长度
	// bits是arr中最大值在BASE进制下有几位
    void radixSort(vector<int>& nums, int n, int bits)
    {
        // 理解的时候可以假设BASE = 10
        for(int offset = 1; bits > 0; offset *= BASE, --bits)
        {
            memset(cnts, 0, sizeof cnts);
            for(int i = 0; i < n; ++i)
            {
                ++cnts[(nums[i] / offset) % BASE]; // 数字提取某一位的技巧
            }
            // 处理成前缀次数累加的形式
            for(int i = 1; i < BASE; ++i) cnts[i] += cnts[i - 1]; 
            // 前缀数量分区的技巧
            // 数字提取某一位的技巧
            for(int i = n - 1; i >= 0; --i)
            {
                help[--cnts[(nums[i] / offset) % BASE]] = nums[i];
            }
            for(int i = 0; i < n; ++i) nums[i] = help[i];
        }
    }

public:
    vector<int> sortArray(vector<int>& nums) 
    {
        if(nums.size() > 1)
        {
            // 如果会溢出，那么要改用long类型数组来排序
            int n = nums.size();
            // 找到数组中的最小值
            int mn = nums[0];
            for(int i = 1; i < n; ++i) mn = min(mn, nums[i]);
            int mx = 0;
            for(int i = 0; i < n; ++i)
            {
                // 数组中的每个数字，减去数组中的最小值，就把arr转成了非负数组
                nums[i] -= mn;
                // 记录数组中的最大值
                mx = max(mx, nums[i]);
            }
            // 根据最大值在BASE进制下的位数，决定基数排序做多少轮
            radixSort(nums, n, bits(mx));
            // 数组中所有数都减去了最小值，所以最后不要忘了还原
            for(int i = 0; i < n; ++i) nums[i] += mn;
        }
        return nums;
    }
};